// 2025/3/24
// 岛屿数量

class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 判断岛屿数量
         * @param grid char字符型vector<vector<>> 
         * @return int整型
         */
        void Sinking(vector<vector<char>>& grid, int i, int j)
        {
            grid[i][j] = '0';
            int m = grid.size(), n = grid[0].size();
            if(i > 0 && grid[i - 1][j] == '1')
                Sinking(grid, i - 1, j);
            if(i < m - 1 && grid[i + 1][j] == '1')
                Sinking(grid, i + 1, j);
            if(j > 0 && grid[i][j - 1] == '1')
                Sinking(grid, i, j - 1);
            if(j < n - 1 && grid[i][j + 1] == '1')
                Sinking(grid, i, j + 1);
        }
    
        int solve(vector<vector<char> >& grid) {
            // write code here
            int m = grid.size(), n = grid[0].size();
            int ans = 0;
            for(int i = 0; i < m; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    if(grid[i][j] == '1')
                    {
                        ans++;
                        Sinking(grid, i, j);
                    }
                }
            }
            return ans;
        }
    };